package leetcode.onehundred;

import java.util.Arrays;

//75. 颜色分类
public class SortColors {

    public static void main(String[] args) {
        int[] nums=new int[]{2,0,2,1,1,0};
        new SortColors().sortColors3(nums);
    }

    public void sortColors(int[] nums) {

        Arrays.sort(nums);
    }


    //p和q指针分别交换0和1
    public void sortColors2(int[] nums) {
        int p = 0;
        int q = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                swap(nums, i, q);
                q++;
            } else if (nums[i] == 0) {
                swap(nums, p, i);
                if (p < q) {
                    swap(nums, i, q);
                }
                p++;
                q++;
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


    //0 挪到最前面，2 挪到最后面就完事儿了
    //注意 2 挪完如果换出来的不是 1，那么指针要回退，因为 0 和 2 都是需要再次移动的
    public void sortColors3(int[] nums) {
        int p = 0;
        int q = nums.length - 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                nums[i] = nums[p];
                nums[p] = 0;
                p++;
            }
            if (nums[i] == 2) {
                nums[i] = nums[q];
                nums[q] = 2;
                q--;
                if (nums[i] != 1) {
                    i--;
                }
            }
        }
    }

}
